package flatten

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

*/
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	// 定义函数f ：将当前结点的左右子树拉平为链表
	var f func(node *TreeNode)
	f = func(node *TreeNode) {
		if node == nil {
			return
		}
		f(node.Left)
		f(node.Right)
		// 采用后序遍历的原因：需要知道左右子树才能拉平链表
		// 后序遍历位置
		left := node.Left   // 临时保存左子树
		right := node.Right // 临时保存右子树

		node.Left = nil   // 拉平链表，左子树置空
		node.Right = left // 原先左子树变成右子树

		pos := node
		for pos.Right != nil {
			pos = pos.Right
		}
		// 原先右子树拼接到现左子树的左儿子上
		pos.Right = right
	}

	f(root)

}
